package com.leetcode.贪心;

import java.util.Arrays;

/**
 * 给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。
 * 返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。
 * 两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。
 * @author LZF
 *
 */
public class L821字符的最短距离 {
	/**
	 * 对于s串中的每一个字符，如果等于c，则该位置的距离为0
	 * 如果不等于c，则距离就是左边离c最近的距离和右边离c最近的距离，两者中取最小的。
	 * 因此对于不等于c的字符，有两个约束条件，一个是左边的c，一个是右边的c
	 * 所以只要遍历两边就可以了：
	 * 第一遍：只考虑左边
	 * 所有的字符考虑左边离c最近的距离，如果左边没有c，则不修改该位置的值。
	 * 第二遍：考虑右边
	 * 所有的字符考虑右边离c最近的距离，然后跟该位置已经存在的值（就是该位置离左边最近的c的距离），取最小值即可。
	 * 
	 * 很明显第一遍遍历的顺序是从前往后，而第二遍遍历的顺序就要从后往前，因为我们需要一个标记，来标记当前右边最近的c在哪里
	 */
	public int[] shortestToChar(String s, char c) {
		int[] answer = new int[s.length()];
		Arrays.fill(answer,Integer.MAX_VALUE);//初始化最大值
		int index = -1;//用来标记c的位置，如果为-1，表示左边（或右边）没有出现c。
		//第一遍，从前往后
		for(int i = 0;i < s.length();i++) {
			if(s.charAt(i) == c) {
				index = i;//更新最近的c的位置
				answer[i] = 0;//等于c的位置的距离为0
			}else {
				if(index != -1) {
					answer[i] = i - index;//因为是遍历左边，因此，i>=index
				}
			}
		}
		
		index = -1;//第二遍时，index需要初始化为-1！！！！！！！！！！！！！！！！！
		
		//第二遍，从后往前
		for(int i = s.length() - 1;i >= 0;i--) {
			if(s.charAt(i) == c) {
				index = i;//更新最近的c的位置
				answer[i] = 0;//等于c的位置的距离为0
			}else {
				if(index != -1) {
					answer[i] = Math.min((index - i),answer[i]);//因为是遍历右边，因此，index >= i
				}
			}
		}
		return answer;
    }
}
